﻿/************************************************************************
 * SMLib - State Model Library
 * Copyright (C) 2012-2013 Ali Khalili (khalili_DOT_ir_@SIGN_gmail_DOT_com)
 * **********************************************************************
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License (LGPL) published 
 * by the Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version. This program is distributed without any
 * warranty. See the GNU Lesser General Public License for more details. 
 * ***********************************************************************
 * File         :     SMLib\Automata\DFA\DFA.cs
 * Description  :     Definition of a deterministic finite automata (DFA)
 * Change log   :     -22 Feb 2013: remove string
*                     -Dec 2012: Initial Version
 * To Do        :     -Minimize DFA
 ************************************************************************/
using System;
using System.Collections.Generic;
using SMLib.Automata.Base;
using SMLib.Base;
using SMLib.Utils;

namespace SMLib.Automata.DFA
{
	/// <summary>
	/// A Deterministic Finite Automaton (DFA) 
	/// <list type="bullet">
	/// <listheader>A DFA is a quintuple (Q,Sigma,Delta,Finally,q0), where</listheader>
	/// <item> 
	/// <description>Q is the non-empty finite set of states</description> 
	/// </item> 
	/// <item> 
	/// <description>Sigma is the alphabet, i.e., the finite set of letters</description> 
	/// </item> 
	/// <item> 
	/// <description>Delta: Q*Sigma to Q, is the transition function</description> 
	/// </item>
	/// <item> 
	/// <description>Finally is a subset of Q is the set of final states</description> 
	/// </item>
	/// <item> 
	/// <description>q0 in Q is the initial state</description> 
	/// </item>
	/// </list> 
	/// <remarks>
	/// To make able which state is accepting or not: accepting states starts with "T"
	/// </remarks>
	/// </summary>
	public class DFA :
    	DiGraph<DFA.DFA_State,DFA.DFA_Transition>
	{
		/// <summary>
		/// Constructor
		/// </summary>
		/// <param name="sigma">The alphabet of DFA</param>
		public DFA (Alphabet sigma)
		{
			this.Sigma = sigma;
		}
		#region DFA Node
		/// <summary>
		/// Nodes of a DFA
		/// <remarks>Identifiers of nodes are "string"</remarks>
		/// </summary>
		public class DFA_State : IState<DFA_Transition>
		{            
			/// <summary>
			/// This state is acceptong or not
			/// </summary>
			public bool isAccepting;
			string id;
			List<DFA_Transition> tr;

			/// <summary>
			/// Constructor
			/// </summary>
			/// <param name="ID">ID of state</param>
			public DFA_State (string ID, bool isAccepting = false)
			{
				id = ID;
				tr = new List<DFA_Transition> ();
				this.isAccepting = isAccepting;
			}

			/// <summary>
			/// Equality of states: reference equality (i.e. two states are equal if they are both point to the same state)
			/// </summary>
			/// <param name="obj">the state to be compared with</param>
			/// <returns></returns>
			public override bool Equals (object obj)
			{
				if (obj is DFA_State) {
					return (obj == this);
				}
				return false;
			}

			/// <summary>
			/// Hash code of the node
			/// </summary>
			/// <returns>hash code of base</returns>
			public override int GetHashCode ()
			{
				return id.GetHashCode ();
			}

			/// <summary>
			/// Find the next state given the input to that state
			/// </summary>
			/// <param name="step">the input</param>
			/// <returns>the next state</returns>
			public DFA.DFA_State NextState (ISymbol step)
			{
				if (step == null)
					return null;

				foreach (DFA.DFA_Transition t in Transitions) {
					if (t.Label.Equals (step)) {
						return (DFA.DFA_State)t.Destination;
					}
				}
				return null;
			}

			/// <summary>
			/// Convert the state into string
			/// </summary>
			/// <returns>the string equivalence</returns>
			public override string ToString ()
			{
				return id.ToString ();
			}
			#region IStateContainer Members
			/// <summary>
			/// Identifier of the state
			/// </summary>
			public object Identifier {
				get { return id; }
			}

			/// <summary>
			/// List of outgoing transitions
			/// </summary>
			public List<DFA_Transition> Transitions {
				get { return tr; }
			}

			/// <summary>
			/// Content of the state
			/// </summary>
			public object content {
				get { return id; }
			}
			#endregion
		}
		#endregion
		#region DFA Transition
		/// <summary>
		/// Transition used in DFA nodes
		/// </summary>
		public class DFA_Transition //: ILabeledTransition<DFA_State, ISymbol>
		{
			DFA_State dst;
			ISymbol label;

			/// <summary>
			/// Constructor
			/// </summary>
			/// <param name="label">label of transition</param>
			public DFA_Transition (ISymbol label)
			{
				dst = null;
				this.label = label;
			}

			/// <summary>
			/// Convert the transition into string. The string value is in fact the value of its label
			/// </summary>
			/// <returns>the equivalent string</returns>
			public override string ToString ()
			{
				return label.ToString ();
			}

			/// <summary>
			/// Set destination of this transition
			/// </summary>
			/// <param name="node">the target node</param>
			public void SetDestination (DFA_State node)
			{
				dst = node;
			}

			/// <summary>
			/// Label of the transition
			/// </summary>
			public ISymbol Label {
				get { return label; }
			}
			#region ITransition Members
			/// <summary>
			/// Destination of transition
			/// </summary>
			public DFA_State Destination {
				get { return dst; }
			}
			#endregion
		}
		#endregion
		/// <summary>
		/// The -input- alphabet
		/// </summary>
		protected Alphabet Sigma;

		/// <summary>
		/// Input alphabet of the DFA
		/// </summary>
		public Alphabet InputAlphabet {
			get {
				return Sigma;
			}
		}



		#region ITransitionSystem<DFA_State,DFA_Transition,ISymbol> Members

        /// <summary>
        /// 
        /// </summary>
        /// <param name="state"></param>
        /// <param name="input"></param>
        /// <returns></returns>
        public List<DFA.DFA_Transition> TransitionsOf (DFA.DFA_State state, ISymbol input)
		{
			List<DFA.DFA_Transition> dsts = new List<DFA_Transition> ();
			foreach (DFA_Transition sym in state.Transitions) {
				if (sym.Label.Equals (input)) {
					dsts.Add (sym);
					return dsts;
				}
			}
			return dsts;
		}

		public ISymbol AssociatedInput (DFA.DFA_Transition t)
		{
			return t.Label;
		}
		#endregion
		/// <summary>
		/// Determines whether a word is accepted or not
		/// </summary>
		/// <returns><c>true</c> if accepted <c>false</c> in other case</returns>
		/// <param name="w">The width.</param>
		public bool IsAccepted (Word w)
		{
			DFA_State tmp = states [0];
			for (int i=0; i<w.Length; i++) {
				bool found = false;
				foreach (DFA.DFA_Transition tr in tmp.Transitions) {
					if (tr.Label.Equals (w [i])) {
						found = true;
						tmp = tr.Destination;
						break;
					}
				}
				if (!found)
					throw new Exception ("Opssss!");
			}
			return tmp.isAccepting;
		}

		public override DFA.DFA_State DestinationOf (DFA.DFA_Transition t)
		{
			return t.Destination;
		}
	}
}
